package LearnAlgorithm.g_数学问题;

import java.util.Scanner;

import LearnAlgorithm.h_标准数学公式.f拓展欧几里得算法;

/*
对任何整数a和b，和它们的最大公约数d，
关于未知数x和y的线性丢番图方程(称为裴蜀等式) :
ax + by = m，有整数解时，当且仅当：m是d的倍数

裴蜀等式有解时，必然有无穷多个整数解，每组解x、y都称为裴蜀数

可用扩展欧几里得算法(Extended Euclidean algorithm)求得

例：
方程12x + 42y=6有解
gcd(12,42) = 6; 6是6的1倍


特别地：方程ax + by = 1有整数解，当且仅当整数a和b互素
 */
public class c裴蜀等式 {
	static double x = 0D;
	static double y = 0D;
	
	public static void main(String[] args) {
		try {
			new f拓展欧几里得算法().foolOperation();//12x + 42y = 6
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public void foolOperation() throws Exception {
		Scanner scanner = new Scanner(System.in);
		System.out.println("线性方程ax + by = m");
		System.out.println("其中a = ");
		double a = scanner.nextDouble();
		System.out.println("其中b = ");
		double b = scanner.nextDouble();
		System.out.println("其中m = ");
		double m = scanner.nextDouble();
		System.out.println("a与b的最大公约数：" + lineEuclideanAlgorithm(a, b, m));
		System.out.println("无数个解中的其中一对解：[" + x + ", " + y + "]");
	}
	
	/**
		线性方程ax + by = m
		当m是gcd(a, b)倍数时有解；即m % gcd(a, b) = 0时有解
		等价于ax = m mod b
	 * @param a
	 * @param b
	 * @param m
	 * @return
	 * @throws Exception
	 */
	public double lineEuclideanAlgorithm(double a, double b, double m) throws Exception {
		double d = extendedEuclideanAlgorithm(a, b);
		if (m % d != 0) {
			throw new Exception("无解!");
		}
		x *= (m / d);//这里为什么*=(m / d)；是因为*=之前求出来的x，y是这个方程“ax + by = gcd(a, b)”的无数个解中的一对解
		y *= (m / d);//gcd(a, b)不一定等于m，但m一定是gcd(a, b)的倍数！多少倍？是(m / gcd(a, b))倍！
		return d;
	}
	
	/**
	 * 拓展欧几里得模板
	 * 调用完成后xy是ax+by-gcd(a, b)的解
	 * @param a
	 * @param b
	 * @return
	 */
	public double extendedEuclideanAlgorithm(double a, double b) {
		if (b == 0D) {//这里是递归出口；也就是最底下的一层的操作；此时a=gcd,b=0
			x = 1D;
			y = 0D;
			return a;
		}
		double res = extendedEuclideanAlgorithm(b, a % b);
		double x1 = x;//声明一个变量来保存上一次的x，因为下面紧接着x就会被改变了
		x = y;//将上一次得y赋值给这一次的x；也就是x = y1
		y = x1 - ((int) (a / b) * y);//将这一次的y赋值；也就是y = x1 - a/b*y1
		return res;
	}
	
	/**
	 * 初始欧几里得模板
	 * @param a
	 * @param b
	 * @return
	 */
	public double gcd(double a, double b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}
